#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

struct BinaryTreeNode // a node in the binary tree
{
	int m_nValue; // value of node
	BinaryTreeNode *m_pLeft; // left child of node
	BinaryTreeNode *m_pRight; // right child of node
};

void OutputPath(BinaryTreeNode* inputNode, int inputNum);
//create bsTree
void CreateBSTree(BinaryTreeNode** inputNode, int value);

vector <int> binaryTreeNum;
int sum = 0;

int main()
{
	//create a binaryTree
	BinaryTreeNode* pRoot = NULL;
	CreateBSTree(&pRoot, 10);
	CreateBSTree(&pRoot, 5);
	CreateBSTree(&pRoot, 4);
	CreateBSTree(&pRoot, 7);
	CreateBSTree(&pRoot, 12);
	/*CreateBSTree(&pRoot, 14);
	CreateBSTree(&pRoot, 12);
	CreateBSTree(&pRoot, 11);
	CreateBSTree(&pRoot, 16);*/

	OutputPath(pRoot, 22);
	system("pause");
	return 0;
}

void CreateBSTree(BinaryTreeNode** inputNode, int value)
{
	if (NULL == *inputNode)
	{
		*inputNode = new BinaryTreeNode();
		(*inputNode)->m_pLeft = NULL;
		(*inputNode)->m_pRight = NULL;
		(*inputNode)->m_nValue = value;
	}
	else
	{
		if (value < (*inputNode)->m_nValue)
		{
			CreateBSTree(&((*inputNode)->m_pLeft), value);
		}
		else if (value > (*inputNode)->m_nValue)
		{
			CreateBSTree(&((*inputNode)->m_pRight), value);
		}
	}
}

void OutputPath(BinaryTreeNode* inputNode, int inputNum)
{
	if (NULL == inputNode)
	{
		//binaryTreeNum.push_back(0);
		return;
	}
	
	binaryTreeNum.push_back(inputNode->m_nValue);
	sum += inputNode->m_nValue;

	if (NULL == inputNode->m_pLeft && NULL == inputNode->m_pRight)
	{
		//binaryTreeNum.push_back(inputNode->m_nValue);
		//for (vector<int>::iterator iter = binaryTreeNum.begin(); iter != binaryTreeNum.end(); ++ iter)
		//{
		//		sum += *iter;
		//}
		if (sum == inputNum)
		{
			for (vector<int>::iterator iter = binaryTreeNum.begin(); iter != binaryTreeNum.end(); ++ iter)
			{
				cout<<*iter<<",";
			}
			cout<<endl;
		}
	}
	else
	{
		//binaryTreeNum.push_back(inputNode->m_nValue);
		OutputPath(inputNode->m_pLeft, inputNum);
		//binaryTreeNum.pop_back();
		OutputPath(inputNode->m_pRight, inputNum);
		//binaryTreeNum.pop_back();
	}

	binaryTreeNum.pop_back();
	sum -= inputNode->m_nValue;
}

//void OutputPath(BinaryTreeNode* inputNode, int inputNum)
//{
//	if (NULL == inputNode)
//	{
//		binaryTreeNum.push_back(0);
//		return;
//	}
//	if (NULL == inputNode->m_pLeft && NULL == inputNode->m_pRight)
//	{
//		binaryTreeNum.push_back(inputNode->m_nValue);
//		int sum = 0;
//		for (vector<int>::iterator iter = binaryTreeNum.begin(); iter != binaryTreeNum.end(); ++ iter)
//		{
//				sum += *iter;
//		}
//		if (sum == inputNum)
//		{
//			for (vector<int>::iterator iter = binaryTreeNum.begin(); iter != binaryTreeNum.end(); ++ iter)
//			{
//				cout<<*iter<<",";
//			}
//			cout<<endl;
//		}
//	}
//	else
//	{
//		binaryTreeNum.push_back(inputNode->m_nValue);
//		OutputPath(inputNode->m_pLeft, inputNum);
//		binaryTreeNum.pop_back();
//		OutputPath(inputNode->m_pRight, inputNum);
//		binaryTreeNum.pop_back();
//	}
//}